[[Combinatorics MOC]]
# Pigeonhole principle

The **pigeonhole principle** is the idea that if $n$ items are put into $m$ containers with $n > m$, 
then at least one of said containers must contain multiple items.

A stronger version states that given $m, k \in \mathbb{N}_{0}$,
and set $I$ of $n:=km+1$ items [[Partition|partitioned]] into sets $\{ S_{i} \}_{i=1}^n$,
then $\abs{S_{i}} \geq k+1$ for some $1 \leq i \leq n$.

## Analogues

- [[Measure theoretic pigeonhole principle]]

#
---
#state/tidy | #lang/en | #SemBr